/*
 * @lc app=leetcode.cn id=437 lang=cpp
 *
 * [437] 路径总和 III
 *
 * https://leetcode.cn/problems/path-sum-iii/description/
 *
 * algorithms
 * Medium (56.85%)
 * Likes:    1354
 * Dislikes: 0
 * Total Accepted:    170K
 * Total Submissions: 300.9K
 * Testcase Example:  '[10,5,-3,3,2,null,11,3,-2,null,1]\n8'
 *
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 *
 * 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
 * 输出：3
 * 解释：和等于 8 的路径有 3 条，如图所示。
 *
 *
 * 示例 2：
 *
 *
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：3
 *
 *
 *
 *
 * 提示:
 *
 *
 * 二叉树的节点个数的范围是 [0,1000]
 * -10^9  
 * -1000  
 *
 *
 */

// @lc code=start
#include <iostream>
#include <unordered_map>
using namespace std;
// Definition for a binary tree node.
/* struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}; */

class Solution {
public:
    // DFS深度优先搜索
    /* // 主函数
    int pathSum(TreeNode *root, int targetSum) {
        return root ? pathSumStartWithRoot(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum) : 0;
    }

    // 辅函数
    int pathSumStartWithRoot(TreeNode *root, long long targetSum) {
        if (!root) {
            return 0;
        }
        int count = root->val == targetSum ? 1 : 0;
        count += pathSumStartWithRoot(root->left, targetSum - root->val);
        count += pathSumStartWithRoot(root->right, targetSum - root->val);
        return count;
    } */

    // 前缀和
    unordered_map<long long, int> prefix;

    int pathSum(TreeNode *root, int targetSum) {
        prefix[0] = 1;
        return dfs(root, 0, targetSum);
    }
    int dfs(TreeNode *root, long long cur, int targetSum) {
        if (!root) {
            return 0;
        }
        int ans = 0;
        cur += root->val;
        if (prefix.count(cur - targetSum)) {
            ans = prefix[cur - targetSum];
        }
        prefix[cur]++;
        ans += dfs(root->left, cur, targetSum);
        ans += dfs(root->right, cur, targetSum);
        prefix[cur]--;
        return ans;
    }
};
// @lc code=end
